//bool hasPathSum(struct TreeNode* root, int targetSum) {
//    if (root == NULL)
//        return false;
//    if (root->val == targetSum && root->right == NULL && root->left == NULL)
//        return true;
//    return hasPathSum(root->left, targetSum - root->val)
//        || hasPathSum(root->right, targetSum - root->val);
//}

//int _sumNumbers(struct TreeNode* root, int prevSum)
//{
//    if (root == NULL)
//        return 0;
//    int sum = prevSum * 10 + root->val;
//    if (root->left == NULL && root->right == NULL)
//        return sum;
//    else
//        return _sumNumbers(root->left, sum) + _sumNumbers(root->right, sum);
//}
//int sumNumbers(struct TreeNode* root) {
//    return _sumNumbers(root, 0);
//}


//class Solution {
//private:
//    int maxSum = INT_MIN;
//
//public:
//    int maxGain(TreeNode* node) 
//    {
//        if (node == nullptr) 
//        {
//            return 0;
//        }
//        int leftGain = max(maxGain(node->left), 0);
//        int rightGain = max(maxGain(node->right), 0);
//
//        int priceNewpath = node->val + leftGain + rightGain;
//        maxSum = max(maxSum, priceNewpath);
//
//        return node->val + max(leftGain, rightGain);
//    }
//
//    int maxPathSum(TreeNode* root) {
//        maxGain(root);
//        return maxSum;
//    }
//};


bool exists(struct TreeNode* root, int level, int k) {
    int bits = 1 << (level - 1);
    struct TreeNode* node = root;
    while (node != NULL && bits > 0) 
    {
        if (!(bits & k)) 
        {
            node = node->left;
        }
        else 
        {
            node = node->right;
        }
        bits >>= 1;
    }
    return node != NULL;
}

int countNodes(struct TreeNode* root) 
{
    if (root == NULL) 
    {
        return 0;
    }
    int level = 0;
    struct TreeNode* node = root;
    while (node->left != NULL)
    {
        level++;
        node = node->left;
    }
    int low = 1 << level, high = (1 << (level + 1)) - 1;
    while (low < high) 
    {
        int mid = (high - low + 1) / 2 + low;
        if (exists(root, level, mid)) 
        {
            low = mid;
        }
        else 
        {
            high = mid - 1;
        }
    }
    return low;
}

